package easy

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	initColor := image[sr][sc]
	var dfs func(grid [][]int, x, y, initColor, newColor int)
	dfs = func(grid [][]int, x, y, initColor, newColor int) {
		m, n := len(grid), len((grid)[0])
		if x >= m || x < 0 || y >= n || y < 0 || (grid)[x][y] != initColor {
			return
		}
		(grid)[x][y] = newColor
		dfs(grid, x-1, y, initColor, newColor)
		dfs(grid, x+1, y, initColor, newColor)
		dfs(grid, x, y-1, initColor, newColor)
		dfs(grid, x, y+1, initColor, newColor)
	}
	if initColor != newColor {
		dfs(image, sr, sc, initColor, newColor)
	}
	return image
}
